/**
 * Created with IntelliJ IDEA.
 * Description:
 * 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
 * 给定的 k 保证是有效的。
 * User: xwl
 */

class ListNode3 {
    int val;
    ListNode next;
    ListNode3(int x) { val = x; }
}

public class Test5 {
    // 找出单向链表中倒数第 k 个节点。返回该节点的值
    public int kthToLast(ListNode head, int k) {
        // 定义俩个节点分别为快慢指针
        ListNode fastNode = head;
        ListNode slowNode = head;
        // 定义一个计数器暂存k
        int count = k - 1;
        // 让快指针先走 k-1 步
        while (count-- != 0) {
            fastNode = fastNode.next;
        }
        // 实现
        while (fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }
        // 此时slow指向的就是倒数第k个节点
        return slowNode.val;
    }
}
